package 题目集.线段树or树状数组.线段树.区间合并问题;

import java.io.*;

/**
 * 最长LR交替子串
 * 给定一个长度为n的字符串，一开始字符串中全是'L'字符
 * 有q次修改，每次指定一个位置i
 * 如果i位置是'L'字符那么改成'R'字符
 * 如果i位置是'R'字符那么改成'L'字符
 * 如果一个子串是两种字符不停交替出现的样子，也就是LRLR... 或者RLRL...
 * 那么说这个子串是有效子串
 * 每次修改后，都打印当前整个字符串中最长交替子串的长度
 * 测试链接 : https://www.luogu.com.cn/problem/P6492
 * 思路：
 *  对于一个父区间，我们可以由左区间或右区间的最大长度与左右区间拼接的来的长度，确定父范围的最大长度。
 *  所以只需维护3个信息,左侧最大长度，右侧最大长度，与自身最大长度,以及最左和最右的字母
 */
public class ch02_最长交替子串 {
    static int n, m;
    static Node[] tree;
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public static void main(String[] args) {
        Reader2 sc = new Reader2();
        n = sc.nextInt();
        m = sc.nextInt();
        int tn = (int) Math.pow(2, Math.ceil(Math.log(n) / Math.log(2)) + 1);
        tree = new Node[tn];
        build(1, 1, n);
        for (int i = 0; i < m; i++) {
            int index = sc.nextInt();
            update(1, index);
            out.println(tree[1].max);
        }
        out.flush();
    }

    public static void build(int i, int l, int r) {
        tree[i] = new Node(l, r);
        if (l == r) return;
        int m = l + r >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m + 1, r);
    }

    public static void update(int i, int index) {
        if (tree[i].l == tree[i].r) {
            tree[i].left = !tree[i].left;
            tree[i].right = tree[i].left;
        } else {
            int m = tree[i].l + tree[i].r >> 1;
            if (index <= m) {
                update(i << 1, index);
            } else {
                update(i << 1 | 1, index);
            }
            pull(i);
        }
    }

    public static void pull(int i) {
        int l = i << 1;
        int r = l | 1;
        int max = Math.max(tree[l].max, tree[r].max);   //左右孩子的最大值
        //是否可以连接
        if (tree[l].right ^ tree[r].left) {
            int join = tree[l].suf + tree[r].pre;
            tree[i].max = Math.max(max, join);
            tree[i].pre = tree[l].max != tree[l].len ? tree[l].pre : tree[l].pre + tree[r].pre;
            tree[i].suf = tree[r].max != tree[r].len ? tree[r].suf : tree[l].suf + tree[r].suf;
        } else {
            tree[i].max = max;
            tree[i].pre = tree[l].pre;
            tree[i].suf = tree[r].suf;
        }
        tree[i].left = tree[l].left;
        tree[i].right = tree[r].right;
    }

    static class Node {
        int l, r, len;
        int max = 1, pre = 1, suf = 1;
        boolean left, right;    //L为false，R为true

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
            len = r - l + 1;
        }
    }

    static class Reader2 {
        static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
        static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

        public Reader2(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }

}
